//好的排序有：快排，希尔，归并，堆排。
//数据结构：数组，链表，栈，堆，队列，树，hashtable，图。
//这些需要自己熟悉。这里讲解qsort库函数排序，bsreach查找。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <time.h>
#include <unistd.h>
#include <sys/timeb.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <errno.h>
#include <fcntl.h> // file option
#include <dirent.h>
// #include <iostream>
// #include <sstream>
// #include <vector>
// #include <list>
// #include <map>
// #include <thread>
// #include <string>
// #include <iomanip>
// #include <fstream>
// #include <vector>
// #include <set>
// #include <algorithm>
// #include <unordered_map>
// #include <mutex>
// #include <atomic>
// #include <bits/wordsize.h>
// #include <bits/timesize.h>
// using namespace std;

//经过测试，100万也是秒排。
#define TEST_SORT_MAX_LEN 10
static int sortBuf[TEST_SORT_MAX_LEN];

//比较函数有规则，返回一定要有：正数，0，负数。
//如果用升序，那么a>b返回正，如果a=b返回0，如果a<b返回负
//如果用降序，那么a>b返回负，如果a=b返回0，如果a<b返回正
//字符串直接可以使用strcmp，因为它返回有这三种值。
//而数字需要a-b。如果返回a>b，只能返回正负两种状态，那么查找可能失败，就有bug。
int mySortCmp(const void *a, const void *b)
{
    const int *c = (const int *)a;
    const int *d = (const int *)b;
    return (*c - *d);
}

int main()
{
    int i;
    int *tmpfind;
    srand(time(NULL));

    for(i = 0; i < TEST_SORT_MAX_LEN; i++)
    {
        sortBuf[i] = rand() % TEST_SORT_MAX_LEN;
    }

    printf("origin data:\n");
    int tmpPrintLen = 100 > TEST_SORT_MAX_LEN ? TEST_SORT_MAX_LEN : 100;
    for(i = 0; i < tmpPrintLen; i++)
    {
        printf("%d ", sortBuf[i]);
    }
    printf("\n");

    printf("begin sort\n");

    qsort(sortBuf, TEST_SORT_MAX_LEN, sizeof(sortBuf[0]), mySortCmp);

    printf("print sort buf data:\n");
    tmpPrintLen = 100 > TEST_SORT_MAX_LEN ? TEST_SORT_MAX_LEN : 100;
    for(i = 0; i < tmpPrintLen; i++)
    {
        printf("%d ", sortBuf[i]);
    }
    printf("\n");

    int tmpval;
    tmpval = rand() % TEST_SORT_MAX_LEN;
    printf("need find = %d\n", tmpval);
    tmpfind = (int *)bsearch(&tmpval, sortBuf, TEST_SORT_MAX_LEN, sizeof(sortBuf[0]), mySortCmp);
    printf("find point = %p\n", tmpfind);
    if(tmpfind == NULL)
    {
        printf("not find:\n");
    }
    else
    {
        printf("find:%d\n", *tmpfind);
    }
}

